1. Field of the Invention
The present invention relates to the field of electronic devices. More specifically, the present invention relates to the area of recognizing a bit pattern in a string of bits, altering the string of bits, and removing the alteration from the string of bits.
2. Background Information
Many electronic devices transmit and/or receive bit streams. For example, two computers may communicate with each other by transmitting and receiving streams of bits. Such communication is often performed by connecting a modem to each computer and transmitting the bit streams over a standard telephone line connecting the modems. Various standards have been adopted for providing this communication, including the International Organization for Standardization Open Systems Interconnection model (ISO/OSI model). The ISO/OSI model uses the HDLC (high-level data-link control) standard for its data-link layer. The HDLC standard breaks down the data to be transmitted into sections, each of which is transmitted in a frame. Each frame starts and ends with a unique, pre-defined pattern of bits that is referred to herein as the "flag" or "frame delimiter". In addition to its section of the data, each frame may also contain information concerning the frame. Upon receiving a frame delimiter, the receiving device knows the following bits up to the next frame delimiter contains a portion of the data. The standard frame contains 256 bytes of data. The use of frames is discussed in "Networking Standards a Guide to OSI, ISDN, LAN and MAN Standards" by William Stallings, Addison-Wesley Publishing Co., 1993. It is worthwhile to note that the notation used in this application identifies the right most bit in a string of bits as the least significant bit and that bit streams are processed from least significant bit to most significant bit.
Since the data to be transmitted may contain the bit pattern used for the frame delimiter, any occurrence of the frame delimiter must be removed from the data to prevent confusion by the receiving device. This is commonly accomplished by using a technique called bit stuffing and stripping. When using this technique, the transmitting device alters the data by stuffing (i.e., inserting) a bit into the data after each occurrence of a search pattern (i.e., a bit pattern which is a portion of the frame delimiter). By altering the data in this pre-defined manner, all occurrences of the frame delimiter may be removed. The receiving device, which is aware of the pre-defined manner in which the data was altered, removes the alterations from the data by stripping the bits stuffed by the transmitting device. Therefore, the receiving device also alters the data in a pre-defined manner to return the data to its original form. For example, if the frame delimiter is "01111110", a useful search pattern would be five consecutive ones. Using this search pattern, the transmitting device will stuff a zero in the data after every series of five consecutive ones. Thus, if the data contains "01111110", the transmitting device will stuff a zero into the data such that it becomes "010111110." Consequently, the receiving device examines the bit following each occurrence of the search pattern in the data. If this bit is a 0, as it is in this example, it is stripped returning the data to its original form. However, if this bit is a 1, a frame delimiter has been received. It is worthwhile to note that the search pattern is not identical to the frame delimiter because the data must be altered in a manner such that the receiving device can systematically remove the stuffed bits from the data.
One prior art method of bit stuffing and stripping is to perform a bit-by-bit inspection of the data to identify occurrences of the search pattern. This method requires a significant amount of processor time. As a result, prior art hardware circuitry has been developed to minimize the main processor's workload.